import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        int max_length=0;//记录相同子串最大长度
        int max_LastIndex=0;//记录字串最后再str1的位置
        int[][] dp=new int[str1.length()+1][str2.length()+1];//dp数组记录相同字符串
for(int i=0;i<str1.length();i++){
    for(int j=0;j<str2.length();j++){
        if(str1.charAt(i)==str2.charAt(j)){
            dp[i+1][j+1]=dp[i][j]+1;
            if(dp[i+1][j+1]>max_length){
                max_length=dp[i+1][j+1];
                max_LastIndex=i;
            }

        }else{
            dp[i+1][j+1]=0;
        }
    }
}
return str1.substring(max_LastIndex-max_length+1,max_LastIndex+1);
    }
}
